package class07;

public class Code05_BobDie {

	/**
	 * 暴力尝试 递归
	 *
	 * @param N
	 * @param M
	 * @param i
	 * @param j
	 * @param K
	 * @return
	 */
	public static String bob1(int N, int M, int i, int j, int K) {
		long all = (long) Math.pow(4, K);
		long live = process(N, M, i, j, K);
		long gcd = gcd(all, live);
		return String.valueOf((live / gcd) + "/" + (all / gcd));
	}

	// N*M的区域，Bob从(row, col)位置出发，走rest步之后，返回值是仍获得生存的方法数
	public static long process(int N, int M, int row, int col, int rest) {
		// 越界了，直接死亡
		if (row < 0 || row == N || col < 0 || col == M) {
			return 0;
		}
		// row, col没越界，但是剩余步数为0，存活下来了
		if (rest == 0) {
			return 1;
		}
		// row, col没越界，但还没走完
		long live = process(N, M, row - 1, col, rest - 1);
		live += process(N, M, row + 1, col, rest - 1);
		live += process(N, M, row, col - 1, rest - 1);
		live += process(N, M, row, col + 1, rest - 1);
		return live;
	}

	public static long gcd(long m, long n) {
		return n == 0 ? m : gcd(n, m % n);
	}
	/*
		用较大的数除以较小的数，得到商和余数；将较小的数作为被除数，余数作为除数，再进行一次相除；
		重复上述步骤，直到余数为零；最后一个非零余数就是最大公约数
	 */


	/**
	 * 严格表结构DP
	 *
	 * @param N
	 * @param M
	 * @param i
	 * @param j
	 * @param K
	 * @return
	 */
	public static String bob2(int N, int M, int i, int j, int K) {
		int[][][] dp = new int[N + 2][M + 2][K + 1];
		for (int row = 1; row <= N; row++) {
			for (int col = 1; col <= M; col++) {
				dp[row][col][0] = 1;
			}
		}
		for (int rest = 1; rest <= K; rest++) {
			for (int row = 1; row <= N; row++) {
				for (int col = 1; col <= M; col++) {
					dp[row][col][rest] = dp[row - 1][col][rest - 1];
					dp[row][col][rest] += dp[row + 1][col][rest - 1];
					dp[row][col][rest] += dp[row][col - 1][rest - 1];
					dp[row][col][rest] += dp[row][col + 1][rest - 1];
				}
			}
		}
		long all = (long) Math.pow(4, K);
		long live = dp[i + 1][j + 1][K];
		long gcd = gcd(all, live);
		return String.valueOf((live / gcd) + "/" + (all / gcd));
	}


	/**
	 * 严格表结构DP--自己写的
	 * @param N
	 * @param M
	 * @param i
	 * @param j
	 * @param K
	 * @return
	 */
	public static String BobDPOwn(int N, int M, int i, int j, int K) {

/*
		// 原递归中越界这部分的basecase。因为只依赖row-1，col-1。row+1，col+1，-1和+1比较固定
		// 越界了，直接死亡
		if (row < 0 || row == N || col < 0 || col == M) {
			return 0;
		}
*/
		// 因此选择 调整dp表的索引范围 防止索引越界的发生


		// 准备一张DP表，存放的是方法数
		// 区域N * M，索引为 [0,N-1]， [0~M-1]
		// 正常情况 比如4个格子N=4，N个格子的索引是[0, 4-1]，
		// 由于防止越界，索引两侧都要加一个点, 范围变为了[-1,4-1+1] (-1,0,1,2,3,4)，总共6个点 （N+2个）
		// 但数组索引从0开始，所有变为[0, 5]，可用范围变为[1, 4]

		int[][][] dp = new int[N + 2][M + 2][K + 1];
		// 初始化  默认初始化即可，方法数为0表示该方法不能使得Bob存活

		// base case
		// row, col没越界，但是剩余步数为0，存活下来了 => 第rest==0层均置为1
		for (int row = 1; row <= N; row++) {
			for (int col = 1; col <= M; col++) {
				dp[row][col][0] = 1;
			}
		}




		// row, col没越界，但还没走完
		for (int rest = 1; rest <= K; rest++) {
			for (int row = 1; row <= N; row++) {
				for (int col = 1; col <= M; col++) {
					dp[row][col][rest] = dp[row - 1][col][rest - 1] // 因为这里有 -1 可能会发生越界，索引
							+ dp[row + 1][col][rest - 1]
							+ dp[row][col - 1][rest - 1]
							+ dp[row][col + 1][rest - 1];
				}
			}
		}

		long all = (long) Math.pow(4, K);
		long live = dp[i+1][j+1][K]; // 因为整体可用的索引范围右移了一个，所以这个也要右移
		long gcd = gcd(all, live);

		return String.valueOf((live / gcd) + "/" + (all / gcd));
	}




	// for test
	public static void main(String[] args) {
		int N = 10;
		int M = 10;
		int i = 3;
		int j = 2;
		int K = 5;
		System.out.println(bob1(N, M, i, j, K));
		System.out.println(bob2(N, M, i, j, K));
		System.out.println(BobDPOwn(N, M, i, j, K));
	}

}